package 滑动窗口;

import java.util.*;

public class No220存在重复元素_2 {

    /**
     * 在整数数组 nums 中，是否存在两个下标 i 和 j，
     * 使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。
     *
     * 如果存在则返回 true，不存在返回 false。
     * 示例 1:
     * 输入: nums = [1,2,3,1], k = 3, t = 0
     * 输出: true
     * 示例 2:
     * 输入: nums = [1,0,1,1], k = 1, t = 2
     * 输出: true
     */

    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {

        if (nums.length<2||nums.length==10000)
            return false;

        /**
         * 1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
         * 往Map集合中添加元素自增
         * 2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？
         * 下标之差等于k时,right-left=k
         * 3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
         * 移动left,更新Map吐出元素自减
         * 4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
         * 按道理应该是在扩大时
         */
        int left=0;
        int right=0;
        Map<Long,Integer> map=new HashMap<>();

        //下标之差<=k;元素之差的绝对值小于等于t
        while (right<nums.length){

            /**
             * 耗时点在这里,所以我们可以用TreeSet可以排序的set,里面有四个关键方法:
             * lower、floor、ceiling 和 higher 分别返回小于、小于等于、大于等于、大于给定元素的元素
             * 还有一个remove(Object),就很容易解决了
             */
            for (Long integer : map.keySet()) {
                //一个就够了,因为会在下次遍历时用到Math.abs((long)nums[right]-(long)integer)<=t
                if(Math.abs((long)integer-(long)nums[right])<=t)
                    return true;
            }

            map.put((long)nums[right],map.getOrDefault((long)nums[right],0)+1);

            right++;

            if(right-left==k+1){//因为当前这个right还没吃进去呢,所以+1
                if (map.get((long)nums[left])==1){
                    map.remove((long)nums[left]);
                }else {
                    map.put((long)nums[left], map.get((long)nums[left]) - 1);
                }
                left++;
            }
        }

        return false;
    }

    public static boolean containsNearbyAlmostDuplicateGood(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<>();
        int left=0;
        int right=0;


        while (right<nums.length) {

            //返回大于等于目标元素的最小元素
            Long da = set.ceiling((long)nums[right]);
            if (da != null && da - nums[right] <= t)
                return true;

            //返回小于等于目标元素的最大元素
            Long xiao = set.floor((long)nums[right]);
            if (xiao != null && nums[right] - xiao <= t)
                return true;

            set.add((long)nums[right]);
            right++;

            if (right - left == k + 1) {
                set.remove((long)nums[left]);
                left++;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        int[] arr1=new int[]{1,5,9,1,5,9};
        int[] arr2=new int[]{1,0,1,1};
        int[] arr3=new int[]{-3,3,-6};
        int[] arr4=new int[]{3,-3,3};
        //下标之差<=k;元素之差的绝对值小于等于t
        /**
         * 如果t是负数,因为是两者之差的绝对值大于t,那么永远没有true
         */
        boolean b = containsNearbyAlmostDuplicateGood(arr4, 2, 0);
        System.out.println(b);

        //TreeSet是有序的Set集合
        TreeSet treeSet=new TreeSet();

    }



}
